/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-06 16:29:03
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-06 16:50:45
 * @FilePath: \LeetCode\46.全排列.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 * 
 * 方法1：使用深度优先搜索
 */

#include <vector>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> v_selected; // 记录选择数字
    std::vector<bool> v_visited; // DFS访问的结点
    int len = 0;                 // nums.length

    void DFS(const std::vector<int> &nums, int i) // i:层数
    {
        if (i == len)
        {
            result.push_back(v_selected);
            return;
        }

        for (int k = 0; k < len; k++)
        {
            if (v_visited[k])
                continue;
            v_visited[k] = true;
            v_selected.push_back(nums[k]);
            DFS(nums, i + 1); // 访问下一层
            v_visited[k] = false;
            v_selected.pop_back();
        }
    }

    std::vector<std::vector<int>> permute(std::vector<int> &nums)
    {
        len = nums.size();
        v_visited.resize(len, false);

        DFS(nums, 0);

        return result;
    }
};
// @lc code=end
